#!/usr/bin/env python
#-*- coding: utf-8 -*-
#__author__:vincentlc
#time: 16/6/1 : 09:57


'''
Given an array of integers and an integer k,
find out whether there are two distinct indices i and j in the array
such that nums[i] = nums[j] and the difference between i and j is at most k.
'''

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if nums == None or len(nums)<2:
            return  False

        dic = dict()
        for i,item in enumerate(nums):
            if item in dic:
                j = dic[item]
                if i-j <= k:
                    return True
            dic[item] = i
        return False
    def containsNearbyDuplicate2(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if nums == None or len(nums)<2:
            return  False

        dic = dict()
        for i,item in enumerate(nums):
            if item in dic:
                j = dic[item]
                if i-j <= k:
                    return True
            dic[item] = i
        return False

cls_a = Solution()
cls_a.containsNearbyDuplicate([1,0,1,1],1)